# 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 
# 
#  你找到的子数组应是最短的，请输出它的长度。 
# 
#  示例 1: 
# 
#  
# 输入: [2, 6, 4, 8, 10, 9, 15]
# 输出: 5
# 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
#  
# 
#  说明 : 
# 
#  
#  输入的数组长度范围在 [1, 10,000]。 
#  输入的数组可能包含重复元素 ，所以升序的意思是<=。 
#  
#  Related Topics 数组 
#  👍 391 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)

        if n < 2:
            return 0
        l = 0
        stack = []
        stack.append(0)

        flag = True
        for i in range(1, n):
            if flag and nums[i] >= nums[stack[-1]]:
                stack.append(i)
            else:
                flag = False
                while len(stack) != 0 and nums[i] < nums[stack[-1]]:
                    stack.pop()

        if len(stack) == 0:
            l = -1
        else:
            l = stack[-1]

        stack.clear()
        stack.append(n - 1)
        flag = True
        for i in range(n - 2, -1, -1):
            if flag and nums[i] <= nums[stack[-1]]:
                stack.append(i)
            else:
                flag = False
                while len(stack) != 0 and nums[i] > nums[stack[-1]]:
                    stack.pop()

        if len(stack) == 0:
            r = n
        else:
            r = stack[-1]

        return max(0, r - l - 1)

    # 也可以先排序，然后比较位置
    def solve(self, nums):
        sortednums = sorted(nums)
        for i in range(len(nums)):
            if nums[i] != sortednums[i]:
                break
        for j in range(len(nums) - 1, -1, -1):
            if nums[j] != sortednums[j]:
                break
        if j <= i:
            return 0

        else:
            return j - i + 1


# leetcode submit region end(Prohibit modification and deletion)

# 2
print(Solution().findUnsortedSubarray([1, 3, 2, 4, 5]))

# 5
print(Solution().findUnsortedSubarray([5, 4, 3, 2, 1]))
#
# # 5
print(Solution().findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]))
# # 6
print(Solution().findUnsortedSubarray([2, 6, 15, 4, 8, 10, 9]))
# # 0
print(Solution().findUnsortedSubarray([1, 2, 3, 4, 5, 6, 7]))
# # 2
print(Solution().findUnsortedSubarray([2, 1]))

print(Solution().findUnsortedSubarray([1]))
